ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpb/data-flow/main.cpp

   1
   2 #include <iostream>
   3 #include <map>
   4 #include <vector>
   5 #include <list>
   6 #include <cassert>
   7
   8 using namespace std;
   9
  10 typedef long long int int64;
  11
  12 #define forsn(i, s, n)  for (int64 i = (s); i < (n); i++)
  13 #define forn(i, n)      forsn (i, 0, n)
  14 #define forall(x, s)    for (typeof((s).begin()) x = (s).begin(); x != (s).end(); x++)
  15
  16 typedef vector<int64> vint;
  17 typedef vector<vint> vvint;
  18
  19 int64 n;
  20 int64 capacidad_eje0;
  21 int64 capacidad_enlace;
  22 vvint grafo;  // listas de adyacencia
  23 vvint costo;  // matriz
  24 vvint flujo;  // matriz
  25
  26 #define agregar(u, v, c) { \
  27         grafo[u].push_back(v); \
  28         costo[u][v] = (c); \
  29         grafo[v].push_back(u); \
  30         costo[v][u] = (c); \
  31 }
  32
  33 #define capacidad(v, w) (((v) == 0 || (w) == 0) ? capacidad_eje0 : capacidad_enlace)
  34
  35 void print_grafo_residual() {
  36         cout << "---------------" << endl;
  37         forn (v, n) {
  38                 cout << v << endl;
  39                 forall (vecino, grafo[v]) {
  40                         cout << "--> ";
  41                         cout << *vecino;
  42                         cout << " costo = " << costo[v][*vecino];
  43                         cout << " flujo = " << flujo[v][*vecino] << " / " << capacidad(v, *vecino);
  44                         cout << endl;
  45                 }
  46                 cout << endl;
  47         }
  48 }
  49
  50 #define INF 0x7fffffff
  51 #define No_hay_camino   -1
  52 #define signo(x)        ((x) < 0 ? -1 : 1)
  53 int64 caumento(vint& camino) {
  54         // buscar el camino de aumento de costo minimo usando Bellman-Ford
  55         vint dist(n, INF);
  56         vint ant(n, -1);
  57
  58         dist[0] = 0;
  59
  60         forn (it, n - 1) {
  61                 // para cada arista del grafo residual
  62                 bool cambio = false;
  63                 forn (v, n) forall (vecino, grafo[v]) {
  64                         const int64 w = *vecino;
  65                         if (capacidad(v, w) - flujo[v][w] <= 0) continue;
  66                         if (dist[v] == INF) continue;
  67                         int64 ndist = dist[v] + signo(flujo[v][w]) * costo[v][w];
  68                         if (ndist < dist[w]) {
  69                                 dist[w] = ndist;
  70                                 ant[w] = v;
  71                                 cambio = true;
  72                         }
  73                 }
  74                 if (!cambio) break;
  75         }
  76
  77         // armar el camino
  78         int64 costo_camino = 0;
  79         int64 actual = n - 1;
  80         while (true) {
  81                 camino.push_back(actual);
  82                 int64 anterior = ant[actual];
  83                 if (anterior == -1) break;
  84                 costo_camino += signo(flujo[anterior][actual]) * costo[anterior][actual];
  85                 actual = anterior;
  86         }
  87         if (actual == 0) {
  88                 return costo_camino;
  89         } else {
  90                 return No_hay_camino;
  91         }
  92 }
  93
  94 int64 resolver() {
  95         int64 flujo_total = 0;
  96         int64 costo_total = 0;
  97         while (flujo_total < capacidad_eje0) {
  98                 //print_grafo_residual();
  99                 vint camino_aumento;
 100                 int64 costo_camino = caumento(camino_aumento);
 101                 if (costo_camino == No_hay_camino) return No_hay_camino;
 102                 // saturar el camino de aumento
 103                 int64 mn = INF;
 104
 105                 forn (i, camino_aumento.size() - 1) {
 106                         const int64 v = camino_aumento[i + 1], w = camino_aumento[i];
 107                         if (flujo[v][w] < 0) {
 108                                 mn = min(mn, -flujo[v][w]);
 109                         } else {
 110                                 mn = min(mn, capacidad(v, w) - flujo[v][w]);
 111                         }
 112                 }
 113                 forn (i, camino_aumento.size() - 1) {
 114                         const int64 v = camino_aumento[i + 1], w = camino_aumento[i];
 115                         flujo[v][w] += mn;
 116                         flujo[w][v] -= mn;
 117                 }
 118                 if (mn == 0) return No_hay_camino;
 119                 flujo_total += mn;
 120                 costo_total += costo_camino * mn;
 121         }
 122
 123         return costo_total;
 124 }
 125
 126 int main() {
 127         int64 m;
 128         while (cin >> n >> m) {
 129                 n++;
 130                 grafo = vvint(n, vint());
 131                 costo = vvint(n, vint(n, 0));
 132                 flujo = vvint(n, vint(n, 0));
 133
 134                 agregar(0, 1, 0);
 135                 forn (i, m) {
 136                         int64 v1, v2, c;
 137                         cin >> v1 >> v2 >> c;
 138                         agregar(v1, v2, c);
 139                 }
 140                 cin >> capacidad_eje0 >> capacidad_enlace;
 141                 int64 r = resolver();
 142                 if (r == No_hay_camino) {
 143                         cout << "Impossible." << endl;
 144                 } else {
 145                         cout << r << endl;
 146                 }
 147         }
 148         return 0;
 149 }
 150